package zt2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
	static int res;
	public static void main(String[] args) {
		ArrayList<A> list=new ArrayList<>();
		list.add(new A(10));
		list.add(new A(20));
		list.add(new A(3));
		list.add(new A(4));
		list.add(new A(18));
		list.add(new A(50));
		while(list.size()>1) {
			A temp=new A();
			Collections.sort(list,new Comparator<A>() {

				@Override
				public int compare(A arg0, A arg1) {
					// TODO Auto-generated method stub
					return arg0.val-arg1.val;
				}
			});	
			A l=list.get(0);
			A r=list.get(1);
			temp.val=l.val+r.val;
			temp.l=l;
			temp.r=r;
			list.remove(l);
			list.remove(r);
			list.add(temp);
		}
		A head=list.get(0);
		dfs(head,0);
		System.out.println(res);
	}
	static void dfs(A head,int chen) {
		if (head==null) {
			return;
		}
		if (head.l==null&&head.r==null) {
			System.out.println(head.val+" "+chen);
			res+=head.val*chen;
			return;
		}
		dfs(head.l, chen+1);
		dfs(head.r, chen+1);
	}
}
class A{
	A l;
	A r;
	int val;
	public A() {
		
	}
	public A(int val) {
		this.val = val;
	}
}

